Lecture’s Plan

  1. What is text clustering?

  2. What are the applications?

  3. How to cluster text data?

Unsupervised learning

Clustering v.s. Classification

Clustering

  • Discover “natural structure” of data

    • What is the criterion?
    • How to identify them?
    • How to evaluate the results?

Clustering

  • Clustering - the process of grouping a set of objects into clusters of similar objects

    • Basic criteria

      • high intra-cluster similarity

      • low inter-cluster similarity

    • No (little) supervision signal about the underlying clustering structure

    • Need similarity/distance as guidance to form clusters

Applications of text clustering

  • Organize document collections

    • Automatically identify hierarchical/topical relation among documents

Applications of text clustering

  • Grouping search results

    • Organize documents by topics

    • Facilitate user browsing

Applications of text clustering

  • Topic modeling
    • Grouping words into topics

Distance metric

Distance metric

  • Basic properties

    • Positive separation
      • \(𝐷(x,y)>0, \forall x \neq y\)
      • \(𝐷(x,y)=0, \mathrm{i.f.f.}, x=y\)
    • Symmetry
      • \(𝐷(x,y)=𝐷(y,x)\)
    • Triangle inequality
      • \(𝐷(x,y)≤𝐷(x,z)+𝐷(z,y)\)

Typical distance metric

  • Minkowski metric

    • \(d(x,y) = \sqrt[p]{\sum^V_{i=1}{(x_i-y_i)^p}}\)

      • When \(p=2\), it is Euclidean distance

  • Cosine metric

    • \(𝑑(x,y)=1−cosine(x,y)\)

      • when \(|x|^2=|y|^2=1\), \(1−cosine(x,y)=\frac{r^2}{2}\)

Typical distance metric

  • Edit distance

    • Count the minimum number of operations required to transform one string into the other

      • Possible operations: insertion, deletion and replacement





← Can be efficiently solved by dynamic programming

Typical distance metric

  • Edit distance

    • Count the minimum number of operations required to transform one string into the other

      • Possible operations: insertion, deletion and replacement

    • Extent to distance between sentences

      • Word similarity as cost of replacement

        • “terrible” -> “bad”: low cost → Lexicon or distributional semantics

        • “terrible” -> “terrific”: high cost → Lexicon or distributional semantics

      • Preserving word order in distance computation

Clustering algorithms

Clustering algorithms

  1. Partitional clustering algorithms
    • Partition the instances into different groups
    • Flat structure
      • Need to specify the number of classes in advance

Clustering algorithms

  1. Hierarchical clustering algorithms
    • Create a hierarchical decomposition of objects
    • Rich internal structure
      • No need to specify the number of clusters
      • Can be used to organize objects

Clustering algorithms

  1. Topic modeling
    • Topic models are a suite of algorithms that uncover the hidden thematic structure in document collections. These algorithms help us develop new ways to search, browse and summarize large archives of texts.
    • We want to find themes (or topics) in documents
    • We don’t want to do supervised topic classification – rather not fix topics in advance nor do manual annotation
    • Need an approach which automatically teases out the topics
    • This is essentially a clustering problem - can think of both words and documents as being clustered

Hard vs. soft clustering

  • Hard clustering: Each document belongs to exactly one cluster

    • More common and easier to do

  • Soft clustering: A document can belong to more than one cluster.

    • Makes more sense for applications like creating browsable hierarchies

    • You may want to put a pair of sneakers in two clusters: (i) sports apparel and (ii) shoes

    • You can only do that with a soft clustering approach.

Partitioning clustering

Partitioning Algorithms

  • Partitioning method: Construct a partition of \(n\) documents into a set of \(K\) clusters

  • Given: a set of documents and the number \(K\)

  • Find: a partition of \(K\) clusters that optimizes the chosen partitioning criterion

    • Globally optimal
      • Intractable for many objective functions
      • Ergo, exhaustively enumerate all partitions
    • Effective heuristic methods: K-means and K-medoids algorithms

Partitioning Algorithms

  • Typical partitional clustering algorithms

    • k-means clustering

      • Partition data by its closest mean

Partitioning Algorithms

  • Typical partitional clustering algorithms

    • k-means clustering

      • Partition data by its closest mean

    • Gaussian Mixture Model

      • Consider variance within the cluster as well

K-Means

  • Assumes documents are real-valued vectors.

  • Clusters based on centroids (aka the center of gravity or mean) of points in a cluster, \(c\):

\[\vec \mu(c)=\frac{1}{|c|}\sum_{\vec a \in c}{\vec x}\]

  • Reassignment of instances to clusters is based on distance to the current cluster centroids.

    • (Or one can equivalently phrase it in terms of similarities)

K-Means Algorithm

  • Select \(K\) random docs \(\{s_1, s_2,… s_K\}\) as seeds.

  • Until clustering converges (or other stopping criterion):

    • For each doc \(d_i\):

      • Assign \(d_i\) to the cluster \(c_j\) such that \(dist(x_i, s_j)\) is minimal.

    • (Next, update the seeds to the centroid of each cluster)

    • For each cluster cj

      • \(s_j = \mu(c_j)\)

K Means Example (K=2)

Termination conditions

  • Several possibilities, e.g.,

    • A fixed number of iterations.

    • Doc partition unchanged.

    • Centroid positions don’t change.

Convergence

  • Why should the K-means algorithm ever reach a fixed point?

    • A state in which clusters don’t change.

  • K-means is a special case of a general procedure known as the Expectation Maximization (EM) algorithm.

    • EM is known to converge.

    • Number of iterations could be large.

      • But in practice usually isn’t

Seed Choice

  • Results can vary based on random seed selection.

  • Some seeds can result in poor convergence rate, or convergence to sub-optimal clusterings.

    • Select good seeds using a heuristic (e.g., doc least similar to any existing mean)

    • Try out multiple starting points

    • Initialize with the results of another method.

K-means issues, variations, etc.

  • Recomputing the centroid after every assignment (rather than after all points are re-assigned) can improve speed of convergence of K-means

  • Assumes clusters are spherical in vector space

    • Sensitive to coordinate changes, weighting etc.

  • Disjoint and exhaustive

    • Doesn’t have a notion of “outliers” by default

    • But can add outlier filtering

Hierarchical clustering

Hierarchical Clustering

  • Build a tree-based hierarchical taxonomy (dendrogram) from a set of documents.

  • One approach: recursive application of a partitional clustering algorithm.incl

Dendrogram: Hierarchical Clustering

  • Clustering obtained by cutting the dendrogram at a desired level: each connected component forms a cluster.

Clustering algorithms

  • Typical hierarchical clustering algorithms

    • Bottom-up agglomerative clustering

      • Start with individual objects as separated clusters
      • Repeatedly merge closest pair of clusters

Clustering algorithms

  • Typical hierarchical clustering algorithms

    • Top-down divisive clustering

      • Start with all data as one cluster

      • Repeatedly splitting the remaining clusters into two

Hierarchical Agglomerative Clustering (HAC)

  • Starts with each doc in a separate cluster

    • then repeatedly joins the closest pair of clusters, until there is only one cluster.

  • The history of merging forms a binary tree or hierarchy.

Closest pair of clusters

  • Many variants to defining closest pair of clusters

    • Single-link
      • Similarity of the most cosine-similar (single-link)
    • Complete-link
      • Similarity of the “furthest” points, the least cosine-similar
    • Centroid
      • Clusters whose centroids (centers of gravity) are the most cosine-similar
    • Average-link
      • Average cosine between pairs of elements

Single Link Agglomerative Clustering

  • Use maximum similarity of pairs:

\[sim(c_i, c_j) = \max_{x \in c_i, y\in c_j}{sim(x,y)}\]

  • Can result in “straggly” (long and thin) clusters due to chaining effect.

  • After merging \(c_i\) and \(c_j\), the similarity of the resulting cluster to another cluster, \(c_k\), is:

\[sim((c_i \cup c_j), c_k) = max(sim(c_i, c_k), sim(c_j, c_k))\]

Complete Link

  • Use minimum similarity of pairs:

\[sim(c_i, c_j) = \min_{x \in c_i, y\in c_j}{sim(x,y)}\]

  • Makes “tighter,” spherical clusters that are typically preferable.

  • After merging \(c_i\) and \(c_j\), the similarity of the resulting cluster to another cluster, \(c_k\), is:

\[sim((c_i \cup c_j), c_k) = min(sim(c_i, c_k), sim(c_j, c_k))\]

Topic Modeling

Topic models

  • Three concepts: words, topics, and documents

  • Documents are a collection of words and have a probability distribution over topics

  • Topics have a probability distribution over words

  • Model:

    • Topics made up of words used to generate documents

Topic models (lda or gensim)

Reality: Documents observed, infer topics

Probabilistic modeling

  1. Treat data as observations that arise from a generative probabilistic process that includes hidden variables: For documents, the hidden variables reflect the thematic structure of the collection.

  2. Infer the hidden structure using posterior inference: What are the topics that describe this collection?

  3. Situate new data into the estimated model: How does this query or new document fit into the estimated topic structure?

Intro to Latent Dirichlet Allocation (LDA)
What is Latent Dirichlet Allocation (LDA)? A generative probabilistic model for collections of discrete data such as text corpora. LDA is a three-level hierarchical Bayesian model, in which each item of a collection is modeled as a finite mixture over an underlying set of latent topics. Each observed word originates from a topic that we do not directly observe. Each topic is, in turn, modeled as an infinite mixture over an underlying set of topic probabilities.
What is used for? The fitted model can be used to estimate the similarity between documents as well as between a set of specified keywords using an additional layer of latent variables which are referred to as topics.
How is it related to text mining and other machine learning techniques? Topic models can be seen as classical text mining or natural language processing tools. Fitting topic models based on data structures from the text mining usually done by considering the problem of modeling text corpora and other collections of discrete data. One of the advantages of LDA over related latent variable models is that it provides well-defined inference procedures for previously unseen documents (LSI uses a singular value decomposition)

LDA Graphical Model

Topic Matrix

The Dirichlet Distribution

  1. The Dirichlet distribution is an exponential family distribution over the simplex, i.e., positive vectors that sum to one

\[p(\theta|\vec a) = \frac{\Gamma(\sum_i{a_i})}{\prod_i{\Gamma(\alpha_i)}}\prod_i{\theta_i^{\alpha_i - 1}}\]

  1. The Dirichlet is conjugate to the multinomial. Given a multinomial observation, the posterior distribution of \(\theta\) is a Dirichlet.

  2. The parameter \(\alpha\) controls the mean shape and sparsity of \(\theta\). Parameter \(\alpha\) is a k-vector with components \(\alpha_i\) >0

  3. The topic proportions are a K dimensional Dirichlet. The topics are a V dimensional Dirichlet.

Geometric Interpretation of LDA

as we draw random variables from theta, I’m going to get distributions over 3 elements.

\(\theta\) ~ Dirichlet(1,1,1) = \(\alpha_1\) = \(\alpha_2\) = \(\alpha_3\) = 1, uniform distribution as an example

Dirichlet is parameterized by \(\alpha\), so as \(\alpha\) increases the chart gets more peaky.

Density Example

When \(\alpha < 1 (s < k)\), you get sparsity and on the 3 simplex you get a figure with increased probability at the corners.

Important piece of info:
  1. The expectations of the posterior (sometimes called M for mean)
  2. The sum of the alphas, which determines the peaky-ness of the Dirichlet
    • If this sum is small, the Dirichlet will be more spread out
    • If large, the Dirichlet will have more peaks at its expectation (sometimes called S for scaling)

LDA Inferences

Posterior distribution & model estimation for LDA

Maximum likelihood (Ml) estimation

Cluster Validation

Desirable properties of clustering algorithms

  • Scalability

    • Both in time and space

  • Ability to deal with various types of data

    • No/less assumption about input data

    • Minimal requirement about domain knowledge

  • Interpretability and usability

Cluster validation

  • Criteria to determine whether the clusters are meaningful

    • Internal validation

      • Stability and coherence

    • External validation

      • Match with known categories

Internal validation

  • Coherence

    • Inter-cluster similarity v.s. intra-cluster similarity

    • Davies–Bouldin index

      • \(DB = \frac{1}{k}\sum_{i=1}^k{\underset{j \neq i}{\operatorname{max}}{(\frac{\sigma_i + \sigma_j}{d(c_i,c_j)})}}\) ← Evaluate every pair of clusters

        • where \(k\) is total number of clusters, \(\sigma_i\) is average distance of all elements in cluster \(i\), \(d(c_i, c_j)\) is the distance between cluster centroid \(c_i\) and \(c_j\).

We prefer smaller DB-index!

Internal validation

  • Coherence

    • Inter-cluster similarity v.s. intra-cluster similarity

    • Dunn index

      • \(D = \frac{ \underset{1 \leq i < j \leq k}{\operatorname{min}}d(c_i, c_j)}{\underset{1 \leq i \leq k}{\operatorname{max}} \sigma_i}\)      We prefer larger D-index!

        • Worst situation analysis

  • Limitation

    • No indication of actual application’s performance

    • Bias towards a specific type of clustering algorithm if that algorithm is designed to optimize a similar metric

External validation

  • Given class label \(\Omega\) ( Required, might need extra cost) on each instance

    • Purity: correctly clustered documents in each cluster

      • \(purity(\Omega,C) = \frac{1}{N}\sum_{i=1}^k{\underset{j}{\operatorname{max}}|c_i \cap w_j|}\) ← Not a good metric if we assign each document into a single cluster
        • where \(c_i\) is a set of documents in cluster \(i\), and \(w_j\) is a set of documents in class \(j\)

\[purity(\Omega, C) = \\ \frac{1}{17}(5 + 4 + 3)\]

External validation

  • Given class label Ω on each instance

    • Normalized mutual information (NMI)

      • \(NMI(\Omega, C) = \frac{I(\Omega, C)}{[H(\Omega)+H(C)]/2}\) ↙ Normalization by entropy will penalize too many clusters
        • where \(I(\Omega, C) = \sum_i \sum_j P(w_i \cap c_j)log{\frac{P(w_i \cap c_j)}{P(w_i)P(c_j)}} \\ H(\Omega) = - \sum_i{P(w_i) logP(w_i)} \ \ \ \mathrm{and} \ \ \ H(C) = - \sum_j{P(c_j)logP(c_j)}\)
      • Indicate the increase of knowledge about classes when we know the clustering results

External validation

  • Given class label \(\Omega\) on each instance

    • Rand index

      • Idea: we want to assign two documents to the same cluster if and only if they are from the same class

      • \(RI = \frac{TP + TN}{TP + FP + FN + TN}\) ← Essentially it is like classification accuracy

External validation

  • Given class label \(\Omega\) on each instance
    • Rand index

External validation

  • Given class label \(\Omega\) on each instance

    • Precision/Recall/F-measure

      • Based on the contingency table, we can also define precision/recall/F-measure of clustering quality

Group Average

  • Similarity of two clusters = average similarity of all pairs within merged cluster.

\[sim(c_i, c_j) = \frac{1}{|c_i \cup c_j|(|c_i \cup c_j| - 1)}\sum_{\vec x \in (c_i \cup c_j)} \sum_{\vec y \in (c_i \cup c_j): \vec y \neq \vec x}{sim(\vec x, \vec y)}\]

  • Compromise between single and complete link.

  • Two options:

    • Averaged across all ordered pairs in the merged cluster

    • Averaged over all pairs between the two original clusters

  • No clear difference in efficacy

Computing Group Average Similarity

  • Always maintain sum of vectors in each cluster.

\[\vec s(c_j) = \sum_{\vec x \in c_j}{\vec x}\] - Compute similarity of clusters in constant time:

\[sim(c_i, c_j) = \frac{\vec s(c_i) + \vec s(c_j) \cdot (\vec s(c_j) + \vec s(c_j)) - (|c_i| + |c_j|)}{(|c_i| + |c_j|)(|c_i| + |c_j| - 1)}\]

What Is A Good Clustering?

  • Internal criterion: A good clustering will produce high quality clusters in which:

    • the intra-class (that is, intra-cluster) similarity is high

    • the inter-class similarity is low

    • The measured quality of a clustering depends on both the document representation and the similarity measure used

External criteria for clustering quality

  • Quality measured by its ability to discover some or all of the hidden patterns or latent classes in gold standard data

  • Assesses a clustering with respect to ground truth … requires labeled data

  • Assume documents with \(C\) gold standard classes, while our clustering algorithms produce \(K\) clusters, \(\omega_1\), \(\omega_2\), …, \(\omega_K\) with \(n_i\) members.

External Evaluation of Cluster Quality

  • Simple measure: purity, the ratio between the dominant class in the cluster \(\pi_i\) and the size of cluster \(\omega_i\)

\[Purity(\omega_i) = \frac{1}{n_i}\max_j(n_{ij}) \ \ \ j \in C\]

  • Biased because having n clusters maximizes purity

  • Others are entropy of classes in clusters (or mutual information between classes and clusters)

Rand index and Cluster F-measure

\[RI = \frac{A + D}{A + B + C + D}\]
Compare with standard Precision and Recall:
\[P= \frac{A}{A + B} \ \ \ \ \ \ P = \frac{A}{A + C}\]
People also define and use a cluster F-measure, which is probably a better measure

Summary

Summary: what did we learn?

  • Text clustering

  • In clustering, clusters are inferred from the data without human input (unsupervised learning)

  • However, in practice, it’s a bit less clear: there are many ways of influencing the outcome of clustering: number of clusters, similarity measure, representation of documents

  • Evaluation

Practical 5